package com.lw.leetcode.stack.c;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * stack
 * 5959. 使数组 K 递增的最少操作次数
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/19 15:21
 */
public class KIncreasing {

    public static void main(String[] args) {
        KIncreasing test = new KIncreasing();


        // 4
        int[] arr = {5, 4, 3, 2, 1};
        int k = 1;

        // 0
//        int[] arr = {4,1,5,2,6,2};
//        int k = 2;

        // 2
//        int[] arr = {4,1,5,2,6,2};
//        int k = 3;

        // 12
//        int[] arr = {12,6,12,6,14,2,13,17,3,8,11,7,4,11,18,8,8,3};
//        int k = 1;

        int i = test.kIncreasing(arr, k);
        System.out.println(i);
    }


    public int kIncreasing(int[] arr, int k) {
        int sum = 0;
        int length = arr.length;
        int[] items = new int[(length + k - 1) / k];
        int index = -1;
        for (int i = 0; i < k; i++) {
            for (int j = i; j < length; j += k) {
                int n = arr[j];
                if (index == -1 || items[index] <= n) {
                    index++;
                    items[index] = n;
                } else {
                    find(items, index, n);
                }
            }
            sum += ((length - i + k - 1) / k - index - 1);
            index = -1;
            Arrays.fill(items, 0);
        }
        return sum;
    }

    private void find(int[] items, int l, int t) {
        int st = 0;
        int end = l;
        while (st < end) {
            int m = st + ((end - st) >> 1);
            if (items[m] > t) {
                end = m;
            } else {
                st = m + 1;
            }
        }
        items[st] = t;
    }

}
